# 两个数组的交集：https://leetcode-cn.com/problems/intersection-of-two-arrays/ 

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """ 使用集合类型 """
        nums1Set = set(nums1)
        rst = set()
        for num in nums2:
            if num in nums1Set: rst.add(num)
        
        return list(rst)


class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """ 排序加双指针, 从头遍历，相等加入结果集， 谁小 谁的指针前移 ， k代表结果集rst最后的元素， 
        新加入的元素不能和 k 对应位置重复"""
        nums1.sort()
        nums2.sort()
        i = j = 0
        k = -1
        rst = list()
        
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                if not rst or rst[k] != nums1[i]:
                    rst.append(nums1[i])
                    k += 1
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1

        return rst    